a = [-7, 1, 2, -1, 3, -2]
n = len(a)

'''线性算法'''
dp = [0] * len(a)  # dp[i] 是以 a[i]结尾的最大子序列的和
dp[0] = a[0]
for i in range(1, n):
    if dp[i - 1] < 0:
        dp[i] = a[i]
    else:
        dp[i] = dp[i - 1] + a[i]

print(dp)

best = max(dp)


print(best)
